package com.nine.algorithm.leetcode.list;

/**
 * @author nine
 * @version 1.0
 * @description 根据值删除节点
 * @date 24/5/4 11:15
 */
public class Leetcode203 {

	/**
	 * 删除链表中等于给定值 val 的所有节点。
	 * 方法一：直接删除
	 *
	 * @param head 链表
	 * @param val  要删除的值
	 * @return
	 */
	public static ListNode removeElements(ListNode head, int val) {
		// 创建一个虚拟头节点，哨兵节点
		ListNode s = new ListNode(-1, head);
		ListNode p1 = s;
		ListNode p2 = s.next;

		// 节点存在值时
		while (p2 != null) {
			if (p2.val == val) {
				// 删除，p2向后平移
				p1.next = p2.next;

				// 也可以 p2 = p1.next; 因为 上一步 p1.next已经指向了 p2.next
				p2 = p2.next;
			}
			else {
				// p1、p2都平移
				p1 = p1.next;

				// 也可以 p2 = p1.next; 因为 上一步 p1 已经指向了 p1.next
				p2 = p2.next;
			}
		}
		// 返回哨兵节点的下一个
		return s.next;
	}

	/**
	 * 方法一：变动，上一步的变化（抽取相同的步骤）
	 *
	 * @param head
	 * @param val
	 * @return
	 */
	public static ListNode removeElements2(ListNode head, int val) {
		// 创建一个虚拟头节点，哨兵节点
		ListNode s = new ListNode(-1, head);
		ListNode p1 = s;

		// ListNode p2 = s.next;
		ListNode p2 = p1.next;
		// 节点存在值时
		// while (p2 != null) {
		while ((p2 = p1.next) != null) {
			if (p2.val == val) {
				// 删除，p2向后平移
				p1.next = p2.next;

				// 也可以 p2 = p1.next; 因为 上一步 p1.next已经指向了 p2.next
				// p2 = p1.next;
			}
			else {
				// p1、p2都平移
				p1 = p1.next;

				// 也可以 p2 = p1.next; 因为 上一步 p1 已经指向了 p1.next
				// p2 = p1.next;
			}
			// p2 = p1.next;
		}
		// 返回哨兵节点的下一个
		return s.next;
	}

	/**
	 * 方法二：递归删除
	 *
	 * @param p
	 * @param val
	 * @return
	 */
	public static ListNode removeElements3(ListNode p, int val) {
		if (p == null) {
			return null;
		}
		// 节点相等
		if (p.val == val) {
			return removeElements3(p.next, val);
		}
		else {
			// 返回自身是，更新一下下一个节点，不然指针就没有变
			p.next = removeElements3(p.next, val);
			return p;
		}
	}

	public static void main(String[] args) {
		ListNode head = ListNode.of(1, 2, 6, 3, 4, 5, 6);
		// ListNode head = ListNode.of(7, 7, 7, 7);
		System.out.println("head = " + head);
		ListNode result = removeElements(head, 6);
		System.out.println("result = " + result);
		ListNode result3 = removeElements3(head, 6);
		System.out.println("result3 = " + result3);
	}
}
